package day_2022_12_to_3.year2023;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author haomin
 * @date 2023/01/08 23:14
 **/
public class Day1_8_Review {
    class Solution21 {
        public int[] exchange(int[] nums) {
            int l = 0, r = nums.length - 1;
            while(l < r) {
                while(l < r && nums[l] % 2 == 1) l++;
                while(l < r && nums[r] % 2 == 0) r--;
                if(l < r) {
                    int temp = nums[l];
                    nums[l] = nums[r];
                    nums[r] = temp;
                }
            }
            return nums;
        }
    }

    class Solution22 {
        // 方法一：栈 先进后出
        public ListNode getKthFromEnd1(ListNode head, int k) {
            Deque<ListNode> s = new LinkedList<>();
            while(head != null) {
                s.push(head);
                head = head.next;
            }
            while(k-- > 1) s.poll();
            return s.poll();
        }

        // 方法二：快慢指针
        public ListNode getKthFromEnd(ListNode head, int k) {
            ListNode n1 = head;
            ListNode n2 = head;
            while(k-- > 0) n1 = n1.next;
            while(n1 != null) {
                n1 = n1.next;
                n2 = n2.next;
            }
            return n2;
        }
    }

    class Solution24 {
        // 方法一：头插法
        public ListNode reverseList1(ListNode head) {
            if(head == null || head.next == null) return head;
            ListNode dummyHead = new ListNode(-1);
            dummyHead.next = null;
            while(head != null) {
                ListNode next =head.next;
                head.next = dummyHead.next;
                dummyHead.next = head;

                head = next;
            }
            return dummyHead.next;
        }

        // 方法二：双指针
        public ListNode reverseList2(ListNode head) {
            if(head == null || head.next == null) return head;
            ListNode pre = null;
            ListNode cur = head;
            while(cur != null) {
                ListNode next = cur.next;
                cur.next = pre;

                pre = cur;
                cur = next;
            }
            return pre;
        }

        // 方法三：递归
        public ListNode reverseList(ListNode head) {
            if(head == null || head.next == null) return head;
            ListNode second = head.next;
            ListNode newHead = reverseList(head.next);

            second.next = head;
            head.next = null;
            return newHead;
        }
    }
}